package offer.diff;

/**
 * @author DengYuan2
 * @create 2021-03-15 19:13
 */
public class n_10_1 {
    public static void main(String[] args) {
        n_10_1 n = new n_10_1();
        int res = n.Fibonacci3(6);
        System.out.println(res);
    }


    public int Fibonacci(int n) {
        if (n <= 1) {
            return n;
        }
        return Fibonacci(n - 1) + Fibonacci(n - 2);
    }

    public int Fibonacci2(int n) {
        if (n == 0) {
            return 0;
        } else if (n == 1) {
            return 1;
        }
        int[] arr = new int[n + 1];
        arr[0] = 0;
        arr[1] = 1;
        for (int i = 2; i <= n; i++) {
            arr[i] = arr[i - 1] + arr[i - 2];
        }
        return arr[n];
    }

    /**
     * 考虑到第 i 项只与第 i-1 和第 i-2 项有关，因此只需要存储前两项的值就能求解第 i 项，从而将空间复杂度由 O(N) 降低为 O(1)
     *
     * @param n
     * @return
     */
    public int Fibonacci3(int n) {
        if (n <= 1) {
            return n;
        }
        int pre1 = 1;
        int pre2 = 0;
        int res = 0;
        for (int i = 2; i <= n; i++) {
            res = pre1 + pre2;
            pre2 = pre1;
            pre1 = res;
        }
        return res;
    }



}
